#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 二分查找
// 704. 二分查找
class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            // 防止溢出，最后+left是因为left不一定为0
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] == target)
                return mid;
        }

        return -1;
    }
};
// 二分查找
// 34. 在排序数组中查找元素的第一个和最后一个位置
/*
    思路：
        使用二分查找找到左右两端点便可确定第一个和最后一个位置
*/
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        if (nums.size() == 0)
            return {-1, -1};

        // 二分查找左端点
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            // 这里不能使用right-left+1，最后只剩两个数时，会让right一直指向mid，导致死循环
            int mid = left + (right - left) / 2;
            // 因为是找左端点，所以nums[mid]可以是大于或者等于，但是不可以是小于，小于便让left指向mid+1
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        int begin = 0;
        // 判断left是否指向了要查找的值，如果没有说明该值不存在
        if (nums[left] != target)
            return {-1, -1};
        else
            begin = left;

        // 二分查找右端点
        right = nums.size() - 1;
        while (left < right)
        {
            // 这里不能使用right-left，最后只剩两个数时，会让left一直指向mid，导致死循环
            int mid = left + (right - left + 1) / 2;
            // 因为是找右端点，所以nums[mid]可以是小于或者等于，但是不可以是大于，大于便让right指向mid-1
            if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid;
        }

        return {begin, right};
    }
};
// 二分查找
// 69. x的平方根
/*
    思路：
        由题意可得：如果x的算术平方根是小数则需要省略小数部分
        那么，所得结果 <= 实际结果，即：满足该条件的最大值
        此时便需要用到二分查找查找右端点的思想
*/
class Solution
{
public:
    int mySqrt(int x)
    {
        if (x < 1)
            return 0;

        // 查找右端点：该数的算数平方根如果是小数，会省略小数部分，所以所得结果可能比实际结果小
        // 所以需要用查找右端点，即：查找满足条件的最大右边界（条件：所得结果 <= 实际结果）
        int left = 1, right = x;
        while (left < right)
        {
            // +1是为了让结果倾向于右侧，避免死循环
            // 为什么要倾向于右侧：因为本题要得出满足某个条件的最大值
            long long mid = left + (right - left + 1) / 2;
            // 结果在左半区间
            if (mid * mid > x)
                right = mid - 1;
            // 结果在右半区间
            else if (mid * mid <= x)
                left = mid;
        }

        return left;
    }
};
// 二分查找
// 35. 搜索插入位置
/*
    思路：
        由题意将该题转换为：查找满足条件的最小值
        即：使用二分查找查找左端点
*/
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target)
                right = mid;
            else if (nums[mid] < target)
                left = mid + 1;
        }
        if (nums[left] < target)
            return left + 1;

        return left;
    }
};
// 二分查找
// 山脉数组的封顶索引
/*
    思路：
        由题意得：查找其中值递增到峰值元素再递减(递增到某个数再递减)
        可转化为：改变单调性的首元素(找到改变单调性的左端点)
        注意：与二分查找的两个模板有些相反，但是是符合山脉数组的结构特点的
*/
// 方法一：查找左端点
class Solution
{
public:
    int peakIndexInMountainArray(vector<int> &arr)
    {
        int left = 1, right = arr.size() - 2;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2; // 中间值偏右
            if (arr[mid - 1] < arr[mid])
                left = mid; // 向右收缩
            else if (arr[mid - 1] > arr[mid])
                right = mid - 1; // 向左收缩
        }

        return left;
    }
};
// 方法二：查找右端点
class
{
    int peakIndexInMountainArray(vector<int> &arr)
    {
        int left = 0, right = arr.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2; // 中间值偏左
            if (arr[mid] < arr[mid + 1])
                left = mid + 1; // 向右收缩
            else
                right = mid; // 向左收缩
        }
        return left;
    }
};
// 二分查找
// 153. 寻找旋转排序数组中的最小值
// 方法一：查找左端点，无需考虑边界问题
/*
    思路：
        按照题意：将最右边的值作为参照物x，左区间内的值都大于x，右区间内的值都小于x
        找出右区间中的左值，便是最后结果，即当前数组的最小值
*/
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        int size = right;
        // 查找左端点
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[size])
                left = mid + 1;
            else if (nums[mid] <= nums[size])
                right = mid;
        }

        return nums[left];
    }
};
// 方法二：查找右端点，需要考虑边界问题
/*
    思路：
        按照题意：将最左边的值作为参照物x，左区间内的值都大于x，右区间内的值都小于x
        找出左区间中的右值，左区间的右值是最大值，那么最大值的下一个数必定是最小值，便是最后结果，即当前数组的最小值
*/
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        int size = left;
        // 查找右端点
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[size])
                left = mid;
            else if (nums[mid] <= nums[size])
                right = mid - 1;
        }

        return right + 1 >= nums.size() ? nums[0] : nums[right + 1];
    }
};
// 二分查找
// LCR 173.点名
/*
    思路：
        1、 找到中间值判断该值是否等于其下标
            等于，则说明缺席值在右区间，则向右缩小
            不等于，则说明缺席值在左区间，则向左缩小
        2、 最后判断找到的值是否等于其下标
            等于，说明缺席值是最后一个值，则返回值+1
            不等于，说明缺席值是 该下标，则返回
*/
class Solution
{
public:
    int takeAttendance(vector<int> &records)
    {
        // 二分查找
        int left = 0, right = records.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid)
                left = mid + 1;
            else
                right = mid;
        }

        return left == records[left] ? records.size() : left;
    }
};